n = 800;
ty = [0,1,1,0,0,1,0,0,0,1,1,1,0,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,0,1,1,0,1,0,0,1,0,1,1,1,1,1,0,1,1,1,0,1,1,1,1,1,1,1,0,1,1,1,1,0,1,1,1,1,0,0,1,0,0,1,0,1,1,1,0,0,0,1,1,1,1,1,1,0,0,0,1,1,1,0,1,1,1,1,0,0,1,0,0,0,1,1,1,1,1,0,1,0,0,1,1,1,1,0,1,1,1,1,0,1,1,1,1,0,1,1,1,1,0,1,1,1,1,0,0,1,1,1,1,1,1,0,1,1,0,0,1,0,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,0,0,0,1,0,0,0,1,0,1,0,0,0,0,1,1,1,0,1,1,1,1,1,0,1,0,1,0,1,1,1,1,1,1,0,1,0,1,0,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,1,1,1,1,1,1,1,0,1,0,0,1,1,1,1,0,1,0,1,1,1,0,1,1,1,0,0,0,1,1,1,1,1,0,1,1,1,1,0,0,1,1,0,1,0,0,1,1,1,0,1,0,0,1,1,1,1,1,1,1,0,0,1,0,1,1,1,1,1,0,1,0,1,1,1,0,1,1,1,1,0,0,1,1,1,1,1,1,1,1,1,0,0,0,1,1,0,0,0,1,0,1,0,1,1,0,1,0,0,1,0,0,0,0,1,1,0,0,1,1,1,1,0,1,0,1,1,0,1,1,1,1,1,0,0,1,0,0,0,0,1,0,0,0,0,1,1,1,1,0,0,1,1,0,1,0,1,1,1,1,0,1,0,0,0,1,1,1,1,1,1,1,1,0,0,1,0,1,0,1,1,0,0,1,1,1,1,0,0,1,1,1,0,0,1,1,0,1,1,1,1,1,1,1,1,1,1,1,0,1,0,1,1,1,1,0,1,1,0,1,1,1,1,1,1,0,1,0,1,1,1,1,1,1,0,1,0,1,1,1,1,1,1,1,1,1,1,0,1,0,1,1,1,1,0,0,1,0,0,1,1,1,1,0,1,1,0,1,1,1,1,1,1,1,1,1,1,0,1,1,1,0,1,0,1,1,1,0,1,1,0,0,1,1,0,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,0,0,1,1,1,1,1,1,0,1,1,1,0,0,0,1,1,0,1,1,0,1,1,0,1,1,1,1,1,1,0,0,1,1,1,1,1,1,0,1,1,1,0,0,1,0,1,1,1,1,1,0,1,0,1,1,1,1,1,1,1,1,1,0,1,0,1,1,1,1,0,0,0,1,0,1,0,1,1,0,0,1,1,1,1,0,0,0,1,1,1,0,1,0,1,0,1,0,1,1,1,0,1,1,0,0,0,1,1,1,1,1,1,1,0,0,1,0,1,0,1,1,0,1,1,1,1,1,0,0,0,1,1,0,1,1,1,0,1,1,1,0,1,0,0,1,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,0,1,0,1,0,0,1,1,0,0,0,1,1,0,1,1,1,1,1,1,1,1,1,1,1,0,1,1,0,1,0,0,1,1,1,0,1,1,1,1,1,1,1,0,1,0,1,1,1,0,1,1,1,0,0,1,0,1,0,0,1,1,1,0,1,0,1,1,1,0,0,1,1,1,1,1,1,0,0,0,0,1,0,1,1,1,0,0,0,0,0,0,1,1,0,0];
price = [278,234,29,953,460,421,701,776,108,504,294,490,107,143,26,212,89,42,55,200,758,106,77,191,33,128,88,61,103,201,213,22,41,3,19,43,5,64,35,15,308,11,377,375,513,212,209,419,710,731,444,350,129,313,482,120,309,447,543,592,19,460,432,278,342,279,32,370,442,702,821,383,21,385,177,281,638,237,324,463,66,248,347,935,532,584,166,288,321,222,266,42,343,157,548,222,150,301,227,105,65,51,30,707,63,3,33,134,714,37,32,86,161,3,858,213,248,322,402,11,346,79,897,302,441,432,111,836,377,367,296,264,265,373,505,54,246,127,45,527,196,307,582,62,96,120,104,62,35,6,687,32,119,126,435,197,179,201,121,195,330,37,137,521,643,604,837,516,80,31,33,95,642,911,400,294,112,274,174,159,162,6,198,574,739,274,212,187,387,541,80,259,212,233,380,79,156,654,119,205,381,259,287,389,380,198,497,131,307,386,482,901,426,433,648,690,777,676,293,324,576,173,917,501,411,435,352,680,758,341,226,732,62,82,87,39,237,262,55,611,214,451,143,285,89,143,100,104,281,740,116,171,280,16,25,27,8,568,532,986,9,21,22,15,31,522,5,15,27,8,465,595,628,371,944,685,629,329,557,87,607,263,129,325,78,84,146,113,61,105,113,97,671,273,115,476,57,57,413,220,282,98,24,919,63,145,32,69,110,64,53,114,894,951,133,35,119,2,36,134,23,22,97,439,185,624,581,774,977,187,256,147,189,266,78,251,98,819,198,135,710,121,550,110,97,461,306,829,421,745,567,823,211,144,306,329,195,322,327,305,391,385,322,146,145,746,428,395,415,347,528,218,277,456,227,242,381,347,307,470,380,525,503,104,233,219,417,450,43,401,55,288,273,243,130,144,826,107,232,56,236,215,172,176,141,384,282,65,174,424,930,598,117,764,404,430,453,115,675,993,659,572,376,256,68,376,124,51,974,112,115,92,44,49,68,84,9,112,90,115,943,79,295,93,374,363,385,140,446,307,658,202,487,454,151,505,223,58,104,345,175,452,34,75,256,8,551,160,292,547,67,440,44,114,48,75,10,448,554,570,69,583,308,277,128,446,401,271,378,35,636,30,68,5,23,58,28,7,911,105,42,35,88,47,108,102,13,100,79,225,279,140,251,371,233,726,107,147,350,335,11,439,525,551,265,280,210,347,302,110,76,3,291,234,382,196,367,163,671,396,337,336,176,93,452,471,330,511,587,804,501,544,835,260,727,109,117,594,191,204,249,404,470,61,158,59,154,492,126,224,343,458,16,193,150,147,260,384,168,274,48,473,425,226,259,239,397,516,119,87,793,503,711,686,84,120,900,145,148,156,147,36,86,156,159,133,96,150,354,612,395,121,343,573,619,230,434,132,128,437,29,490,120,445,56,316,179,406,95,527,373,257,645,670,356,628,635,492,876,367,927,212,483,327,896,285,157,84,214,137,210,327,372,239,147,129,201,853,486,324,493,187,712,163,194,433,226,64,144,550,686,382,491,708,229,372,418,9,775,362,912,290,668,423,10,100,18,685,22,12,2,12,23,22,10,10,1,18,14,429,285,233,12,15,137,5,582,56,414,150,142,24,21,215,152,205,1,240,440,410,28,120,443,173,105,305,263,181,65,206,71,328,693,107,22,339,5,4,19,67,50,34,27,38,54,77,59,444,44,29,73,7,8,66,57,95,5,81,121,142,874,25,840,666,98,100,59,417,35,283,122,148,76,555,467,303,868,802,180,742,682,841,568,264,13,23,282,5,11,3,995,196,648,983,467,671,264,685,242,117];
time = [290,311,312,316,326,328,329,330,331,332,333,334,649,651,676,677,678,680,681,682,683,684,685,686,687,688,689,690,691,692,693,962,964,969,971,985,1000,1001,1002,1003,1004,1005,1006,1026,1052,1053,1054,1055,1056,1057,1058,1059,1060,1061,1062,1063,1064,1065,1066,1067,1068,1069,1070,1098,1100,1107,1130,1142,1167,1173,1204,1207,1208,1209,1254,1275,1282,1283,1284,1285,1286,1287,1288,1289,1290,1291,1292,1293,1294,1295,1296,1297,1298,1309,1314,1316,1337,1339,1341,1344,1345,1346,1350,1351,1376,1418,1420,1465,1495,1497,1500,1503,1505,1506,1508,1509,1514,1544,1545,1546,1547,1548,1549,1550,1551,1552,1553,1554,1555,1556,1557,1558,1588,1620,1622,1623,1626,1627,1628,1629,1630,1631,1632,2185,2206,2207,2217,2223,2224,2225,2226,2227,2228,2348,2366,2387,2388,2390,2391,2392,2611,2626,2637,2640,2643,2644,2645,2646,2647,2648,2649,2650,2651,2652,2653,2654,2655,2688,2694,2721,2724,2729,2767,2772,2777,2800,2803,2804,2805,2806,2807,2808,2809,2810,2811,2856,2887,2889,2894,2916,2927,2941,2944,2945,2949,2953,2957,2958,2959,2960,2968,2986,2995,2996,2997,2998,2999,3000,3001,3002,3003,3004,3005,3006,3007,3008,3009,3010,3011,3012,3013,3038,3042,3049,3050,3051,3052,3053,3054,3055,3056,3057,3064,3095,3098,3101,3102,3103,3104,3105,3106,3107,3108,3627,3656,3657,3658,3659,3660,3661,3662,3663,3664,3665,3666,3667,3668,3669,3670,3671,3701,3712,3714,3717,3730,3740,3741,3742,3743,3744,3745,3764,3795,3796,3822,3854,3856,3858,3860,3861,3862,3863,3864,3865,3866,3971,3973,4006,4008,4014,4015,4047,4076,4087,4089,4090,4091,4931,4934,4944,4963,4964,4965,4966,4967,4968,4969,4970,4971,4972,4973,4974,4975,5170,5201,5204,5207,5211,5212,5426,5436,5443,5444,5453,5455,5458,5459,5460,5461,5464,5466,5467,5468,5469,5470,5495,5509,5529,5534,5535,5536,5537,5538,5539,5568,5596,5598,5599,5600,5601,5602,5603,5604,5605,5606,5607,5608,5609,5610,5611,5612,5893,5913,5920,5929,5966,5967,5977,5985,5988,5993,5998,6000,6001,6002,6004,6005,6006,6007,6008,6009,6010,6530,6535,6683,6697,6719,6720,6721,6722,6723,6724,6725,6726,6727,7021,7046,7049,7050,7051,7052,7053,7054,7055,7056,7057,7058,7059,7060,7061,7062,7063,7064,7065,7166,7169,7182,7185,7187,7191,7197,7199,7200,7201,7202,7203,7205,7206,7207,7208,7209,7210,7234,7262,7263,7264,7265,7267,7268,7269,7270,7271,7272,7273,7274,7275,7276,7277,7278,8003,8009,8019,8025,8034,8043,8044,8045,8047,8085,8096,8103,8105,8111,8114,8115,8119,8120,8121,8122,8123,8124,8125,8126,8127,8128,8129,9024,9033,9065,10018,10019,10029,10033,10036,10056,10565,10573,10583,10584,10587,10600,10602,10603,10604,10605,10606,10607,10608,10609,10636,10638,10652,10667,10668,10669,10670,10671,10672,10673,10674,10675,10676,10677,10678,10679,10680,10681,10688,10694,10699,10707,10713,10714,10715,10716,10717,10718,10719,10720,10721,10722,10723,10724,10725,10746,10774,10781,10782,10783,10784,10785,10786,10787,10788,10789,10790,10794,10800,10810,10830,10835,10839,10849,10870,10871,10872,10873,10874,10875,10876,10877,10878,10879,11109,11122,11148,11149,11150,11151,11152,11153,11187,11211,11216,11229,11231,12175,12201,12211,12212,12215,12216,12218,12219,13072,13104,13105,13106,13107,13108,13109,13110,13111,13112,13113,13114,13115,13116,13119,13122,13144,13146,13148,13149,13150,13151,13152,13153,13154,13155,13156,13157,13158,13159,13160,13161,13162,13163,13195,13215,13222,13251,13265,13266,13958,13981,13989,13992,13993,13994,13995,13996,13997,13998,13999,14000,14001,14002,14410,14437,14440,14441,14442,14443,14444,14445,14446,14447,14448,14449,14450,14451,14452,14453,14454,15006,15021,15042,15046,15048,15049,15050,15071,15089,15098,15105,15730,15766,15767,15768,15769,15770,15771,15772,15773,15774,16762,16775,16783,16786,16792,16794,16795,16796,16797,16798,16799,16800,16801,16802,16803,16804,16805,16806,17656,17681,17693,17696,17700,17713,17750,17755,17756,17757,17767,17784,17787,18218,18238,18240,18249,18250,18251,18252,18253,18254,18255,18256,18257,18258,18259,18260,18261,18262,18274,18291,18300,18311,18316,18317,18340,18343,18347,18348,18349,18350,18351,18352,18353,18354,18355,18356,18357,18358,18359,18360,18361,18794,18815,18818,18819,18825,18827,18828,18829,18830,18831,18832,18833,18834,18835,18836,18837,18838,18987,19005,19012,19013,19026,19027,19028,19029,19030,19031,19052,19068,19084,19089,19090,19094,19096,19113,19156,19157,19373,19374,19408,19415,19882,20038];